package com.tgy.cmp;

import com.tgy.Sort;

/**
 * @Author: tgy
 * @Date: 2020-11-16 17:30
 */
public class InsertionSort01<E> extends Sort<E> {

    @Override
    protected void sort() {


        for (int i = 1; i < elements.length; i++) {

            int local = find(i);

            if (local == i) {
                continue;
            }

            E element = elements[i];
            for (int j = i; j > local ; j--) {

                elements[j] = elements[j - 1];
            }

            elements[local] = element;
        }

    }

    public int find(int index) {

        int left = 0, right = index, mid;

        while (left != right) {

            mid = (left + right) >> 1;

            if (compare(index,mid) <= 0) {

                right = mid;
            }else {

                left = mid + 1;
            }
        }

        return left;
    }
}
